/*
 * @lc app=leetcode.cn id=128 lang=cpp
 *
 * [128] 最长连续序列
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // unordered_set<int> hash;
        // for (const int & num: nums) {
        //     hash.insert(num);
        // }
        // int ans = 0;
        // while (!hash.empty()) {
        //     int cur = *(hash.begin());
        //     hash.erase(cur);
        //     int next = cur + 1, prev = cur - 1;
        //     while (hash.count(next)){
        //         hash.erase(next++);
        //     }
        //     while (hash.count(prev)) {
        //         hash.erase(prev--);
        //     }
        //     ans = max(ans, next - prev - 1);
        // }
        // return ans;
        // 卧槽这玩意还能用哈希？

        // 那本书的作者简单粗暴的用了哈希set
        // 这玩意不像multiple_set，在插入的时候一个值只有一个
        // 多插了也没用，反正插完没重复数了
        // count也只有0和1了
        
        // 还有看了下哈希的begin返回的迭代器
        // 不指定时候返回所有链最开始有数的那个链的第一个数
        // 还能指定begin(n)、end(n)返回第n个链表内的迭代器
        
        // 反正他就硬查，有加减1的就删了接着查

        // 还能并查集？这个nb啊
    // unordered_map<int,int>mp,fa,cnt;
    // int longestConsecutive(vector<int>& nums) {
    //     if(nums.size()==0) return 0;
        
    //     int ans=1;
    //     for(auto i:nums){
    //         mp[i]=1; cnt[i]=1; fa[i] = i;
    //     }
    //     for(auto i:nums){
    //         if(mp[i+1]==1){
    //             ans = max(merge(i,i+1),ans);
    //         } 
    //     }
    //     return ans;
    // }
    // int find(int x){
    //     if(fa[x]!=x) fa[x]=find(fa[x]);
    //     return fa[x];
    // }
    // int merge(int i, int j){
    //     int x = find(i),y = find(j);
    //     if(x == y){
    //         return cnt[x];
    //     }
    //     fa[y] = x;// j结点的父亲变为i节点的父亲（合并）
    //     cnt[x]+=cnt[y];// i结点下的数量+=本来连在j上的点的数量
        
    //     return cnt[find(i)];
    // }

        // 啊我太菜了，光是sort()就超了log(n)了
        if (nums.size() == 0){return 0;}
        sort(nums.begin(), nums.end());
        int currentLength = 1;
        int currentMax = 1;
        for (int i=0;i<nums.size()-1;++i){
            if (nums[i+1] == nums[i]){
                continue;
            }
            if (nums[i+1] == nums[i] + 1){
                currentLength++;
            }else{
                if (currentLength > currentMax){
                    currentMax = currentLength;
                }
                currentLength = 1;
            }
        }
        if (currentLength > currentMax){
            currentMax = currentLength;
        }
        return currentMax;
        // [0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
    }
};
// @lc code=end

